package org.nowcoder.leetcode.DP;

/**
 * Title  : 152. Maximum Product Subarray
 * Source : https://leetcode.cn/problems/maximum-product-subarray/description/
 * Author : XrazYang
 * Date   : 2023-12-22
 */

public class LeetCode_152 {
    public int maxProduct(int[] nums) {
        //定义状态: maxDp[i]，表示以num[i]结尾的连续数组的最大乘积
        int[] maxDp = new int[nums.length];

        //定义状态: minDp[i]，表示以num[i]结尾的连续数组的最小乘积
        int[] minDp = new int[nums.length];

        //2. 初始状态
        maxDp[0] = nums[0];
        minDp[0] = nums[0];

        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxDp[i] = Math.max(maxDp[i - 1] * nums[i], Math.max(minDp[i - 1] * nums[i], nums[i]));
            minDp[i] = Math.min(maxDp[i - 1] * nums[i], Math.min(minDp[i - 1] * nums[i], nums[i]));
            max = Math.max(max, maxDp[i]);
        }

        return max;
    }
}
